package com.berchen.数据结构.栈;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 通过栈实现计算器
 * 中缀表达式 前缀表达式 后缀表达式
 */
public class Calculator {

    /**
     * 计算数据 将运算表达式进行计算并且得到值
     * <p>
     * 1.将34×5-2 拆分成 34，×,5,-,2这样的集合
     * 2.将中缀表达式 转成后缀表达式
     * 3.将后缀表达式进行计算得到值 并且返回
     *
     * @param expression
     * @return
     */
    public double calculate(String expression) {

        // 数据校验
        expression=dataValid(expression);
        if(expression==null){

            throw new RuntimeException("表达式格式错误");
        }

        // 1.将34×5-2 拆分成 34，×,5,-,2这样的集合
        List<String> infix = expressionToList(expression);
        // 2.将中缀表达式 转成后缀表达式
        List<String> suffix=infixToSuffix(infix);
        // 3.将后缀表达式进行计算得到值 并且返回
        return suffixToNum(suffix);
    }

    public static void main(String[] args) {

        String regix=".{1,}\\d";
        System.out.println("*12.".matches(regix));
        System.out.println("1234".substring(0, 3));
    }

    /**
     * 数据处理
     * @param str
     * @return
     */
    private String dataValid(String str){

        try {
            if(str.isEmpty()){
                return null;
            }
            str=str.replace("X","*");
            str=str.replace("x","*");
            str=str.replaceAll("[ ]{1,}","");
            System.out.println(str);
            // 去除表达式结尾不是数字的数据
            String regix=".{1,}\\d";
            while (!str.matches(regix)){
                str=str.substring(0,str.length()-1);
            }
            return str;
        }catch (Exception e){
            return null;
        }
    }

    /**
     * 根据后缀表达式计算值
     * @param suffix
     * @return
     */
    private double suffixToNum(List<String > suffix){

        Stack<Double> s=new Stack<>();
        for(int i =0;i<suffix.size();i++){

            String str=suffix.get(i);
            try{
                double num = Double.parseDouble(str);
                s.push(num);
            }catch (NumberFormatException e){
                s.push(calculate(s.pop(),s.pop(),str.charAt(0)));
            }
        }
        return s.pop();

    }

    /**
     * 中缀表达式转后缀表达式
     * @param infix
     * @return
     */
    private List<String> infixToSuffix(List<String> infix){

        List<String > suffix=new ArrayList<>();
        Stack<Character> s1=new Stack<>();  // 用来保存运算符和()

        for(int i=0;i<infix.size();i++){

            String str=infix.get(i);
            
            try{
                Double.parseDouble(str);
                suffix.add(str);
            }catch (NumberFormatException e){
                char ch=str.charAt(0);
                // 不是数值
                // 该符号是运算符
                if(isOperator(ch)) {
                    //判断s1是否为空 或者栈顶元素是(
                    if (s1.size() == 0 || s1.peek()=='(') {
                        s1.push(ch);
                    }
                    else if(getPriority(ch)>getPriority(s1.peek())){
                        s1.push(ch);
                    }
                    else if(getPriority(ch)<=getPriority(s1.peek())){
                        do {
                            suffix.add(s1.pop()+"");
                        }
                        while (s1.size()!=0&&isOperator(s1.peek())&&getPriority(ch)<=getPriority(s1.peek()));
                        s1.push(ch);
                    }
                }else {// 该符号不是运算符
                    // 1 判断是否是(
                    if (str.equals("(")) {
                        s1.push(ch);
                    }
                    // 判断是否是) 直接弹出栈中打运算符加入到suffix中 并且抵消掉左边的(
                    if (str.equals(")")) {
                        while (s1.size() != 0 && s1.peek()!='(') {
                            suffix.add(s1.pop() + "");
                        }
                        s1.pop();
                    }
                }
            }

        }
        // 
        while (s1.size()!=0){
            suffix.add(s1.pop()+"");
        }
        return suffix;
    }


    private List<String> expressionToList(String expression) {

        List<String> list = new ArrayList<>();
        char[] chars = expression.toCharArray();
        String str = "";
        for (int i = 0; i < expression.length(); i++) {

            if (isOperator(chars[i])||chars[i]=='('||chars[i]==')') {
                if(str.length()!=0) {
                    list.add(str);
                    str = "";
                }
                list.add(chars[i] + "");
            } else {
                str += chars[i];
                if (i == expression.length() - 1) {   // 最后一个数字
                    list.add(str);
                    str = "";
                }
            }
        }

        return list;
    }

    /**
     * 判断是否是运算符
     *
     * @param operator
     * @return
     */
    private boolean isOperator(char operator) {

        return operator == '+' || operator == '-' || operator == '*' || operator == '/';
    }

    /**
     * 计算
     *
     * @param num1
     * @param num2
     * @param operator
     * @return
     */
    private double calculate(double num1, double num2, char operator) {
        if (operator == '+') {
            return num1 + num2;
        }
        if (operator == '*') {
            return num1 * num2;
        }
        if (operator == '-') {
            return num2 - num1;
        }
        if (operator == '/') {
            return num1 / num2;
        }
        throw new RuntimeException("运算符错误");
    }

    /**
     * 获取运算符打优先级
     *
     * @return
     */
    private int getPriority(char priority) {
        int result = -1;
        switch (priority) {
            case '+':
                result = 1;
                break;
            case '-':
                result = 1;
                break;
            case '*':
                result = 2;
                break;
            case '/':
                result = 2;
                break;
            default:
                break;
        }
        return result;

    }
}
